package medium

import (
	. "GoLeetcode/common"
)

/*
时间复杂度:O(MN)
空间复杂度:O(MN)
*/

type pair struct {
	x int
	y int
}

var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func maxAreaOfIsland(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	var dfs func(x, y int) int
	dfs = func(x, y int) int {
		// 先判断坐标是否合法,不合法直接返回
		if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0 {
			return 0
		}
		if grid[x][y] == 2 {
			return 0
		}
		grid[x][y] = 2
		count := 0

		for _, d := range dirs {
			count += dfs(x+d.x, y+d.y)
		}
		return count + 1
	}

	var result int
	for i, rows := range grid {
		for j, _ := range rows {
			if grid[i][j] == 1 {
				result = Max(result, dfs(i, j))
			}
		}
	}
	return result
}
